`
https://leetcode.cn/problems/find-k-pairs-with-smallest-sums/ 
`

/**
 * @param {number[]} nums1
 * @param {number[]} nums2
 * @param {number} k
 * @return {number[][]}
 */
var kSmallestPairs = function (nums1, nums2, k) {
  const pq = new Heap((a, b) => a[0] + a[1] - b[0] - b[1])

  for (let i = 0; i < nums1.length; i++) {
    // [ num1 的值, num2 的值, num2 的索引 ]
    pq.push([nums1[i], nums2[0], 0])
  }

  const res = []

  while (k--) {
    const cur = pq.pop()
    const nextIndex = cur[2] + 1
    if (nextIndex < nums2.length) {
      pq.push([cur[0], nums2[nextIndex], nextIndex])
    }
    res.push([cur[0], cur[1]])
  }

  return res
};

class Heap {
  constructor(compare) {
    this.heap = [];
    this.compare = compare;
  }
  size() {
    return this.heap.length;
  }
  isEmpty() {
    return this.heap.length === 0;
  }
  push(value) {
    this.heap.push(value);
    this.bubbleUp(this.heap.length - 1);
  }
  bubbleUp(index) {
    while (index > 0) {
      const parentIndex = Math.floor((index - 1) / 2);
      if (this.compare(this.heap[index], this.heap[parentIndex]) < 0) {
        [this.heap[index], this.heap[parentIndex]] = [this.heap[parentIndex], this.heap[index]];
        index = parentIndex;
      } else break;
    }
  }
  pop() {
    if (this.isEmpty()) return undefined;
    const top = this.heap[0];
    const last = this.heap.pop();
    if (!this.isEmpty()) {
      this.heap[0] = last;
      this.sinkDown(0);
    }
    return top;
  }
  sinkDown(index) {
    let current = index;
    const length = this.size();
    while (true) {
      const left = 2 * current + 1;
      const right = 2 * current + 2;
      let target = current;
      if (left < length && this.compare(this.heap[left], this.heap[target]) < 0)
        target = left;
      if (right < length && this.compare(this.heap[right], this.heap[target]) < 0)
        target = right;
      if (target !== current) {
        [this.heap[current], this.heap[target]] = [this.heap[target], this.heap[current]];
        current = target;
      } else break;
    }
  }
}